package middle;

/**
 * 给定一个m x n 二维字符网格board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母不允许被重复使用。
 * 链接：https://leetcode-cn.com/problems/word-search
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class WordSearch {
    /**
     * DFS
     * 首先找到数组中开始的位置  传给DFS函数
     * 该函数对字符串进行匹配，由于访问过的单元格是无法访问的，故需要一个相同大小的二维数组来记录
     * 当数组的下标[i][j]值为1时，则表示 对应的ij已经被访问过了
     * */
    class Solution {
        public boolean exist(char[][] board, String word) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if(board[i][j] == word.charAt(0)){
                        int[][] flag = new int[board.length][board[0].length];
                        if(DFS(board, i, j, flag, 1, word)){
                            return true;
                        }
                    }
                }
            }
            return false;
        }

        /**
         * i 和 j表示当前位置在board的ij
         * flag是访问标记的数组
         * k是匹配到word的第几个字符
         * word是要被匹配的字符串
         *
         * 代码优化方案 ： 把判断越界或者字符不相等 放在最前面 直接返回false
         * */
        public boolean DFS(char[][] board, int i,int j, int[][] flag, int k, String word){
            if(k == word.length()){
                return true;
            }
            flag[i][j] = 1;
            boolean result = false;
            // 从 右、下、左、上来对word进行匹配
            if(j+1 < board[0].length && flag[i][j+1] != 1 && word.charAt(k) == board[i][j+1]){
                result = DFS(board, i, j+1, flag, k+1, word);
            }
            if(i+1 < board.length && flag[i+1][j] != 1 && word.charAt(k) == board[i+1][j]){
                result = result || DFS(board, i+1, j, flag, k+1, word);
            }
            if(j-1 >= 0 && flag[i][j-1] != 1 && word.charAt(k) == board[i][j-1]){
                result = result || DFS(board, i, j-1, flag, k+1, word);
            }
            if(i-1 >= 0  && flag[i-1][j] != 1 && word.charAt(k) == board[i-1][j]){
                result = result || DFS(board, i-1, j, flag, k+1, word);
            }
            if(!result){
                flag[i][j] = 0;
            }
            return result;
        }
    }
}
